#define DEBUG
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;
const int maxn=100000;

int min(int a, int b) {
  return a<b ? a : b;
}

int max(int a, int b) {
  return a>b ? a : b;
}

class SAM {
public:
  int size, len[4*maxn+1], link[4*maxn+1], next[4*maxn+1][5];

  void init() {
    size = 0;
    link[0] = -1;
  }

  int add(int last, int c) {
    int cur = next[last][c] = ++size, p, q, clone;
    len[cur] = len[last]+1;
    for (p=link[last]; p>=0 && !next[p][c]; p=link[p]) {
      next[p][c] = cur;
    }
    if (p<0) {
      link[cur] = 0;
    } else {
      q = next[p][c];
      if (len[q]==len[p]+1) {
        link[cur] = q;
      } else {
        clone = ++size;
        memcpy(next[clone], next[q], 5*sizeof(int));
        link[clone] = link[q];
        len[clone] = len[p]+1;
        link[cur] = clone;
        link[q] = clone;
        next[p][c] = clone;
        for (p=link[p]; p>=0 && (!next[p][c] || next[p][c]==q); p=link[p]) {
          next[p][c] = clone;
        }
      }
    }
    return cur;
  }

  void get(int s[], int pos[]) {
    int o=0, now=0;
    for (int i=1; i<=s[0]; i++) {
      for (; o>=0 && !next[o][s[i]]; o=link[o]);
      if (o>=0) {
        now = min(now, len[o])+1;
        o=next[o][s[i]];
      } else {
        o=0;
        now = 0;
      }
      pos[i] = max(i-now+1, 1);
    }
  }
};

int getNode(char c) {
  return (c=='A'||c=='a') ? 1 : ((c=='C'||c=='c') ? 2 : ((c=='T'||c=='t') ? 3 : 4));
}

int isHigh(char c) {
  return c>='A' && c<='Z';
}

int main() {
#ifdef DEBUG
  freopen("src.in", "r", stdin);
  freopen("src.out", "w", stdout);
#endif

  int q;
  scanf("%d", &q);

  static char str[maxn+2];
  static int s[maxn+1], pos[maxn+1];
  static SAM t;
  t.init();
  int last=0;
  scanf("%s", str);
  for (int i=0; str[i]; i++) {
    last = t.add(last, getNode(str[i]));
  }

  for (int i=1; i<=q; i++) {
    scanf("%s", str);
    s[0] = 0;
    for (int i=0; str[i]; i++) {
      s[++s[0]] = getNode(str[i]);
    }
    t.get(s, pos);

    static int lim[5];
    for (int i=1; i<=4; i++) {
      lim[i] = 2;
    }
    scanf("%s", str);
    for (int i=0; str[i]; i++) {
      lim[getNode(str[i])] = isHigh(str[i]);
    }

    static ll f[2][16];
    ll ans=0;
    memset(f, 0, sizeof f);
    for (int h=1, t=1, y=0; t<=s[0]; t++) {
      int o=t%2, x=1<<(s[t]-1);
      y^=x;
      memset(f[o], 0, sizeof f[o]);
      for (int i=0; i<16; i++) {
        f[o][i^x] += f[!o][i];
      }
      f[o][x]++;

      for (; h<pos[t]; h++) {
        f[o][y]--;
        y ^= (1<<(s[h]-1));
      }

      for (int i=0; i<16; i++) {
        bool flag=true;
        for (int j=1; flag && j<=4; j++) {
          if (lim[j]<2 && ((i>>(j-1))&1)!=lim[j]) flag=false;
        }
        ans = ans+flag*f[o][i];
      }
    }
    printf("%lld\n", ans);
  }

  fclose(stdin);
  fclose(stdout);
  return 0;
}
